Arithmetic coding was introduced by Rissanen, "Generalized Kraft Inequality and Arithmetic Coding," IBM Journal of Research and Development, Volume 20, No. 3, May 1976, at pp. 198-203. Next, Langdon et al, U.S. Pat. No. 4,122,440, "Method and Means for Arithmetic String Coding," Oct. 24, 1978, taught that arithmetically encoded strings could be compressed to an efficiency approximating, within a predetermined amount, the entropy. The advance in this case relied on using only a limited amount of information from the last code word generated in order to calculate the new code word. Consequently, an encoder/decoder became physically realizable because a buffer of only a finite length was required. However, the applications were restricted because of the manner by which the code characters were generated, i.e. shifting to the "right". This resulted in a last in, first out (LIFO) decoding. LIFO decoding, while suitable for storage codes, was not suitable for point-to-point serial transmission and reception, i.e. satellite communications. Such serial transmission and reception invites a first in, first out (FIFO) decoding operation performable in near real time and permitting continuous adjustment within the receiver.
Since a number is being encoded or generated to represent symbol strings, the LIFO method and means of Langdon et al imports that the least significant bits are generated first, while the most significant bits are generated last. Consequently, decoding cannot occur until the entire codestring has been received and/or assembled. In FIFO operations, the most significant bits are generated first and hence decoding can occur without delay. One example of a FIFO string encoding is to be found in R. C. Pasco, "Source Coding Algorithms for Fast Data Compression," Doctoral Thesis, Department of Electrical Engineering, Stanford University, May 1976.
Pasco disclosed a method of arithmetic string coding in which the updating of the encoded string uses the multiplication operation performed upon operands selected according to their relative probabilities of symbol occurrence. Significantly, Pasco's use of multiplication for updating requires that for each m bit operand multiplied by an n bit operand, then m+n bits of precision must be maintained. As pointed out at page 60 of his thesis, Pasco encoded each new value to the right of the already decoded string. Although FIFO decoding is possible, it requires the processing of the entire string prior to transmission and/or storage. It mitigates against transmission and near real time decoding as the string is generated. The reason for this is that there is no control of "carries."
The arithmetic encoding process can be viewed as the summation of properly shifted numbers as may be found, for example, in the process of ordinary multiplication. Individual summands are termed augends and the displacements in digits between adjacent augends are called shift amounts. In this regard, see Langdon et al and Rissanen and Langdon, "Arithmetic Coding," IBM Journal of Research and Development, Volume 23, No. 2, pp. 149-162, March 1979. In ordinary multiplication, some augends may be 0, as in arithmetic coding, but the shift amount is always 1. Also, in ordinary multiplication, as in LIFO type arithmetic codes, each augend is added to the sum of the previous right-most augend. In ordinary multiplication, this is called partial product. For arithmetic coding purposes, it is termed a partial sum. Once bit positions have exited the arithmetic part of the summation operation, they are never changed. In LIFO arithmetic codes, the summation begins at the least significant augend, whereas for the FIFO codes, the summation begins with the most significant augend. For FIFO codes, the carry-over presents a problem in generating the partial sums beginning with the most significant augend because bit positions which have already undergone the summation process are still subject to being "one-upped" due to the propagation of a carry. The carry-over problem is mentioned in Rissanen and Langdon, but is not treated there. In Pasco, the higher order part of the codestring was retained so any carry could be propagated as far as necessary.